/**
 *  @file test.c
 *  @desc 判断链表 head2 是否为 head1 的连续子序列（匹配值和顺序）
 *  @author WangBlue(wangjiping596@gmail.com)
 *  @date 2025-07-17 16:59
 *  @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// ------------------------- 结点结构定义 -------------------------

/**
 * @brief 单链表结点定义
 */
typedef struct node {
    int data;              ///< 数据域
    struct node *next;     ///< 指针域
} node, *link;

// ------------------------- 链表基本操作 -------------------------

/**
 * @brief 创建一个新的结点
 * @param value 数据值
 * @return 成功返回新结点指针，失败返回 NULL
 */
link createNode(int value) {
    link node = (link)malloc(sizeof(node));  // 动态申请内存
    if (node == NULL) return NULL;
    node->data = value;       // 设置数据域
    node->next = NULL;        // 指针域初始化为 NULL
    return node;
}

/**
 * @brief 头插法插入结点（插在头部）
 * @param head 链表头指针地址（指针的指针，允许修改头指针）
 * @param value 插入的数据
 */
void insertHead(link *head, int value) {
    link node = createNode(value);
    if (!node) return;
    node->next = *head;   // 新结点指向原头结点
    *head = node;         // 头指针更新为新结点
}

/**
 * @brief 尾插法插入结点（插在尾部）
 * @param head 链表头指针地址
 * @param value 插入的数据
 */
void insertTail(link *head, int value) {
    link node = createNode(value);
    if (!node) return;

    if (*head == NULL) {
        // 空链表时，新结点为头指针
        *head = node;
        return;
    }

    // 否则遍历到末尾插入
    link cur = *head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = node;  // 将新结点接到尾部
}

/**
 * @brief 打印链表所有元素
 * @param head 链表头指针地址
 */
void printLink(link *head) {
    if (*head == NULL) return;
    link cur = *head;
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

/**
 * @brief 释放链表的所有结点内存
 * @param head 链表头指针地址
 */
void destroy(link *head) {
    if (*head == NULL) return;
    link cur = *head;
    while (cur != NULL) {
        link temp = cur->next;
        free(cur);
        cur = temp;
    }
    *head = NULL;
    printf("SUCCESS\n");
}

// ------------------------- 判断子序列函数 -------------------------

/**
 * @brief 判断链表 *l2 是否为链表 *l1 的连续子序列
 * @param l1 主链表（被匹配）
 * @param l2 子链表（目标序列）
 * @return true 表示 *l2 是 *l1 的连续子序列；false 否
 *
 * @note 匹配条件为：l1 中存在一段连续子链，其所有元素值与 l2 中完全一致，顺序一致
 */
bool isSubsequence(link *l1, link *l2) {
    if (*l1 == NULL || *l2 == NULL) return false;

    link pa = *l1;  // 从 l1 的头节点开始逐个尝试匹配
    while (pa) {
        link lb = *l2;  // 每次从 l2 开头开始匹配
        link paa = pa;  // 暂存 l1 的当前位置

        // 尝试连续匹配 l2 中所有结点
        while (lb != NULL && paa != NULL && lb->data == paa->data) {
            paa = paa->next;
            lb = lb->next;
        }

        // 如果 l2 遍历完成，说明全部匹配成功
        if (lb == NULL) {
            return true;
        }

        // 否则，主链表往后移动一个结点，再尝试新的起点
        pa = pa->next;
    }

    return false;  // 所有起点都尝试过仍未匹配成功
}

// ------------------------- 主函数测试 -------------------------

int main() {
    link head1 = NULL; // 初始化链表 head1

    // head1 插入数据：4 → 2 → 3
    insertTail(&head1, 4);
    insertTail(&head1, 2);
    insertTail(&head1, 3);

    link head2 = NULL; // 初始化链表 head2

    // head2 插入数据：4 → 1
    insertTail(&head2, 4);
    insertTail(&head2, 1);

    // 判断 head2 是否为 head1 的连续子序列
    bool flag = isSubsequence(&head1, &head2);

    if (flag == true) {
        printf("head2 is head1's sequence\n");
    } else {
        printf("head2 is NOT head1's sequence\n");
    }

    // 建议补充释放内存（当前未调用 destroy）

    return 0;
}
